Entwicklung und Analyse von Algorithmen für realitätsnahe Rechnermodelle

Projektleitung und Mitarbeiter

Niedermeier, R. (Doktorand), Reinhardt, K. (Dr. rer. nat.), gemeinsam mit: Kunde, M. (Dr. rer. nat.), Rossmanith, P. (Dr. rer. nat.), beide Inst. f. Informatik, TU München

Mittelgeber : DFG

Forschungsbericht : 1994-1996

Tel./ Fax.:

Projektbeschreibung

Neben der abstrakteren Suche nach einer praxisrelevanten parallelen Komplexitätstheorie wird im Rahmen des DFG-Drittmittelprojektes KOMET auch konkret die Entwicklung und Analyse von Algorithmen für realitätsnahe Parallelrechnermodelle, wie z. B. gitterförmig verbundene Prozessoren, betrieben. Hierbei werden auch untere Schranken für die zugrundeliegenden Modelle studiert und oft ist es auch möglich, Algorithmen anzugeben, die diese Schranken fast erreichen. Außerdem werden auch Analysen des durchschnittlichen Laufzeitverhaltens im Gegensatz zum Worstcase-Verhalten durchgeführt. Dabei stellten sich signifikante Unterschiede und Laufzeitverbesserungen heraus. Das als Basis bzw. "Prototyp" zugrundeliegende Problem war in diesem Feld in der Regel das Sortierproblem.

Publikationen

Kunde, M., Niedermeier, R., Reinhardt, K., Rossmanith, P.: Optimal average case sorting on arrays. In: Proc. 12th Symposium on Theoretical Aspects of Computer Science (STACS '95) (Mayr, E. W., Puech, C., ed.), Number 900 in Lecture Notes in Computer Science, München, pp. 503 514. Springer 1995.

INDEX HOME SUCHEN KONTAKT LINKS

qvf-info@uni-tuebingen.de(qvf-info@uni-tuebingen.de) - Stand: 30.11.96
Copyright Hinweise